1. Field of the Invention
The present invention pertains in general to image matching, image retrieval, object recognition and object tracking, and more particularly to a method and system for image matching using line signatures.
2. Discussion of Related Art
There are many existing methods for image matching. Most wide-baseline image matching methods are based on local features such as Scale Invariant Feature Transform (SIFT), shape context, Harris corner, and Speeded Up Robust Features (SURF). Repeatability and distinctiveness are two criteria used to evaluate a local feature. Repeatability is the ability that a counterpart of a feature in one image can be detected in the other image even under significant image deformation. Distinctiveness is the description of a feature should be similar to that of its corresponding feature while being very different from the description of any other feature. Often there is trade-off between repeatability an distinctiveness.
Most existing methods rely on local features which are pixel-based. In these pixel-based features each feature is a group of pixels in a connected local region. Typically, the connected region is of a rectangular shape in SIFT and the traditional template matching, the circular area in Shape context, and the elliptical region in Harris-Affine features. However, under large image deformation, it is common that similar regions in two images cannot be enclosed by templates with a fixed shape without including a considerable part of the background totally different in the two images. This is one of the reasons that the repeatability of the above local features decreases rapidly with view point change. Most feature descriptors use some kind of histograms, such as the histograms used in SIFT, Shape Context and Gradient Location-Orientation Histogram (GLOH). Histograms with fixed bin size are not distinctive when image distortion is large. Some descriptors are based on moments which can handle large deformation of planar patterns but have limited power to deal with non-planar distortion such as parallax change.
One of the problems in using local features is to detect feature correspondences under large image deformation caused by viewpoint change (especially for non-planar scenes), zooming and lighting variation. Most existing local features also have difficulties in matching images without rich texture.
Sketch signature which is based on curves instead of pixel solves some the above outlined problems. In sketch signature, curves are extracted from images and divided into contour segments including straight line segments and elliptical segments. A sketch signature is a cluster of nearby segments with an arbitrary spatial distribution. The number of segments in a sketch signature directly controls its distinctiveness. Since the number of its segments is small, it is also much easier to design a descriptor that can explicitly handle large image distortion.
There exist a certain amount of work on line-based image matching. The conventional line-based matching approaches can be divided into two types: matching individual line segments and matching groups of segments. Among the approaches of matching individual line segments, some methods match line segments based on their orientation and length and usually use a nearest line strategy. These methods are useful only when the images are very similar and are better suited to image tracking or small-baseline stereo. Some methods start with matching individual segments and resolve ambiguities by enforcing a weak constraint that adjacent line matches have similar disparities, or by checking the consistency of segment relationships, such as left of, right of, connectedness, etc. These methods require known epipolar geometry but cannot handle large image deformation. Many of these methods are computationally expensive for solving global graph matching problems.
Other line-based matching methods exploit the color distribution of the pixels on both sides of each segment, which is only reliable under small illumination change.
Perceptual grouping of line segments is widely used in object recognition and detection. It is based on perceptual properties such as connectedness, convexity, and parallelism so that segments are more likely on the same object. Although this strategy is useful to reduce searching space in detecting the same objects in totally different backgrounds, it is not suited to image matching since it is quite often that the only detectable fragment on the boundary of an object is indistinctive but it can form a distinctive feature with several neighboring fragments on different objects whose configuration is stable in a considerable range of viewpoint changes. As a result, many features very useful in image matching may be lost. In addition, the conventional line-clustering method does not provide a mechanism to handle spurious segments that may greatly deteriorate feature repeatability. Furthermore, the feature descriptor in the conventional line-segment clustering approach is only scale and rotation invariant. Therefore, these methods are limited and can suffer when other image transformations, such as large deformation including affine deformation, perspective distortion and parallax are applied.
The present invention addresses various issues relating to the above.